package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

@SuppressWarnings("all")
public class _46_全排列 {

    // 输入：nums = [1,2,3]
    // 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    private List<List<Integer>> resultList;
    private Stack<Integer> stack;
    private int[] nums;
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        this.resultList = new ArrayList<>();
        if (nums == null || nums.length == 0) return resultList;
        this.nums = nums;
        this.stack = new Stack<>();
        this.used = new boolean[nums.length];
        dfs(0);
        return resultList;
    }

    private void dfs(int level) {
        if (level == nums.length) {
            resultList.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            stack.push(nums[i]);
            used[i] = true;
            dfs(level + 1);
            // return就是从i+1层回到i层，并遍历第i层的n+1个元素
            // 在第i层重新选择元素，要将之钱遍历过的第n个元素的状态还原
            stack.pop();
            used[i] = false;
        }
    }
}
